package leetcode;

import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-30 16:07
 **/
import java.util.HashMap;
import java.util.Map;

public class LeetCode399 {

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int n = equations.size();
        //2 * equationsSize 表示equations任意两个变量都不相同,最极端情况下的容量
        UnionFind uf = new UnionFind(2 * n);
        // 第 1 步：预处理，将变量的值与 id 进行映射，使得并查集的底层使用数组实现，方便编码
        Map<String, Integer> map = new HashMap<>(2 * n);
        int id = 0;

        for (int i = 0; i < n; ++i) {
            String str1 = equations.get(i).get(0);
            String str2 = equations.get(i).get(1);
            if (!map.containsKey(str1)) {
                map.put(str1, id);
                ++id;
            }

            if (!map.containsKey(str2)) {
                map.put(str2, id);
                ++id;
            }

            uf.union(map.get(str1), map.get(str2), values[i]);
        }

        int size = queries.size();
        double[] res = new double[size];
        // 第 2 步：做查询
        for (int i = 0; i < size; ++i) {
            String str1 = queries.get(i).get(0);
            String str2 = queries.get(i).get(1);

            Integer id1 = map.get(str1);
            Integer id2 = map.get(str2);
            if (id1 == null || id2 == null) {
                res[i] = -1.0d;
            } else {
                res[i] = uf.isConnected(id1, id2);
            }
        }
        return res;
    }
}

//加权并查集
class UnionFind {
    int[] parent;
    double[] weight;

    /**
     * 构造方法,初始化并查集数组和权值数组
     * @param n
     */
    public UnionFind(int n) {
        parent = new int[n];
        weight = new double[n];

        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            weight[i] = 1.0d;
        }
    }

    void union(int x, int y, double value) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return;
        }

        //将x的根节点指向y的根节点
        parent[rootX] = rootY;
        //修改x根节点的权值
        weight[rootX] = weight[y] * value / weight[x];

    }

    /**
     * 路径压缩
     */
    int find(int x) {

        if (x != parent[x]) {
            int val = parent[x];
            //递归使得x节点到根节点路径上的所有节点指向根节点
            parent[x] = find(parent[x]);
            //每一个节点的权值都是对根节点权值的倍数
            weight[x] *= weight[val];
        }

        return parent[x];
    }

    double isConnected(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        //如果x,y属于统一集合,则返回其运算的值,否则返回-1.0d
        if (rootX == rootY) {
            return weight[x] / weight[y];
        } else {
            return -1.0d;
        }
    }
}

